课程名称：算法设计与分析
参考往年题来源：TheBloodthirster/BUAA_Course_Sharing
数据结构二叉树线索二叉树(Threaded Binary Tree）利用二叉链表中空的指针域指出结点在某种遍历序列中的直接前驱或直接后继
指向前驱和后继的指针称为线索
实现不用栈的树深度优先遍历算法
二叉查找树(Binary Search Tree, BST）左子树都更小，右子树都更大
建立：逐点插入法
平衡二叉树(Adelson-Velskii and Landis, AVL）左子树和右子树的深度之差的绝对值不超过1
最坏情况下插入和查找的时间复杂度为O(log2n)
堆(Heap)一种特殊类型的二叉树
（1）每个节点的值大于（或小于）等于其每个子节点的值
（2）该树完全平衡，其最后一层的叶子都处于最左侧的位置。
大顶堆的根节点包含了最大的元素，小顶堆的根节点包含了最小的元素
哈夫曼树(Huffman Tree）给定一组权值，构造出的具有最小带权路径长度(WPL, weighted path length)的二叉树
优先队列(Priority queue）权值越大的叶结点离根结点越近，权值越小的叶结点离根结点越远
多叉树B树(Balanced Tree)m阶B树是平衡的m路搜索树
根结点至少有两个孩子；
每个非根节点所包含的孩子个数 \(j\) 满足：\(\lceil m/2 \rceil \leq j \leq m\)
每个叶节点的关键字个数 \(k\) 满足：\(\lceil m/2 \rceil- 1 \leq k \leq m - 1\)
具有 n 棵子树的结点中一定有n 个关键字
key[i] 和 key[i+1] 之间的孩子节点的值介于 key[i] 和 key[i+1] 之间
所有的叶子结点都位于同一层
2-3树最简单的B树结构每个非叶节点都有两个或三个子女，而且所有叶都在统一层上B+树B树基础上
叶结点中存放记录的关键字以及指向记录的指针
叶结点按关键字值的大小顺序